720B - Cactusophobia - CodeForces Solution

#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
using namespace std;
#define db double
const int maxn = 30005;
vector<pi> eg[maxn];
int fa[maxn], dep[maxn], fcolor[maxn];
int cnt[maxn];
vector<vi> cycs;
void dfs(int a) {
    for (auto e : eg[a]) {
        int v = e.fi, c = e.se;
        if (dep[v]) {
            if (dep[v] < dep[a] && v != fa[a]) {
                vi cur;
                int p = a;
                while (1) {
                    cur.pb(fcolor[p]);
                    p = fa[p];
                    if (p == v) break;
                }
                cur.pb(c);
                cycs.pb(cur);
            }
        }
        else {
            dep[v] = dep[a] + 1;
            fa[v] = a;
            fcolor[v] = c;
            dfs(v);
        }
    }
}
#define maxm 255010
#define inf 200000
using namespace std;
struct edge
{
	int u, v, c;
	edge *rev;
	edge *next;
}pool[maxm * 2], *h[maxn];
int ecnt = 0;
void addedge(int u, int v, int c)
{
	//cout<<"ADE"<<u<<" "<<v<<" "<<c<<endl;
	edge *new1 = &pool[ecnt++];
	new1->u = u, new1->v = v, new1->c = c;
	
	edge *new2 = &pool[ecnt++];
	new2->u = v, new2->v = u, new2->c = 0;
	
	new1->rev = new2, new2->rev = new1;
	new1->next = h[u], h[u] = new1;
	new2->next = h[v], h[v] = new2;
}
int level[maxn], q[maxn], fr, ed;
int s, t;
void bfs()
{
	fr = ed = 0;
	memset(level, -1, sizeof(level));
	level[s] = 1, q[ed++] = s;

	while(fr < ed)
	{
		for(edge *p = h[q[fr]]; p; p = p->next)
		{
			if(!p->c || level[p->v] != -1) continue;
			level[p->v] = level[q[fr]] + 1, q[ed++] = p->v;
		}
		fr++;
	}
}
int dfs(int a, int flow)
{
	if(!flow) return 0;
	if(a == t) return flow;
	int nf = 0;
	for(edge *p = h[a]; p; p = p->next)
	{
		if((level[p->v] != level[a] + 1) || (p->c <= 0)) continue;
		int nflow = dfs(p->v, min(flow - nf, p->c));
		nf += nflow, p->c -= nflow, p->rev->c += nflow;
	}
	if(!nf) level[a] = -1;
	return nf;
}
int dinic()
{
	int ans = 0;
	while(1)
	{
		bfs();
		int nans = dfs(s, inf);
		if(!nans) break;
		ans += nans;
	}
	return ans;
}
int ids[maxn];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        eg[u].pb(mp(v, c));
        eg[v].pb(mp(u, c));
        cnt[c] += 1;
    }
    dep[1] = 1;
    dfs(1);
    int ans = 0;
    int idcnt = 0;
    for (int i = 0; i < maxn; i++)
        if (cnt[i]) ans += 1, ids[i] = ++idcnt;
    
    ans -= cycs.size();
    s = cycs.size() + idcnt + 1;
    t = s + 1;
    for (int i = 0; i < cycs.size(); i++) {
        addedge(s, i + 1, 1);
        for (auto c : cycs[i]) 
            addedge(i + 1, cycs.size() + ids[c], 1);
    }
    for (int i = 0; i < maxn; i++) 
        if (ids[i])
            addedge(cycs.size() + ids[i], t, cnt[i] - 1);
    ans += dinic();
    cout << ans << endl;
    return 0;
}